

public class SLoj {
        public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }



    public static ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead==null){
            return null;
        }
        ListNode ae=null,ax=null;
        ListNode be=null,bx=null;
        while(pHead!=null){
            if(pHead.val<x){
                if(ae==null){
                    ae=ax=pHead;
                }else{
                    ax.next=pHead;
                    ax=ax.next;
                }
            }else{
                if(be==null){
                    be=bx=pHead;
                }else{
                    bx.next=pHead;
                    bx=bx.next;
                }
            }
            pHead=pHead.next;
        }
        if(ae==null)
            return be;
        if(be==null)
            return ae;
        bx.next=null;
        ax.next=be;
        return ae;
    }

    public static void display(ListNode phead){
        ListNode pcur=phead;
        while (pcur!=null){
            System.out.print(pcur.val+" ");
            pcur=pcur.next;
        }
        System.out.println();
    }



    public static void main1(String[] args) {
        ListNode l1=new ListNode(1);
        ListNode l2=new ListNode(8);
        ListNode l3=new ListNode(4);
        ListNode l4=new ListNode(6);

        l1.next=l2;
        l2.next=l3;
        l3.next=l4;

        ListNode ph=partition(l1,5);
        display(ph);

    }



}
